package JZOffer;

/**
 * 剑指 Offer 14- I. 剪绳子
 * 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），
 * 每段绳子的长度记为 k[0],k[1]...k[m-1] 。
 * 请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？
 * 例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
 * **/

class Solution14_1 {
    public int cuttingRope(int n) {
        //长度为1的绳子没法剪了
        if (n <= 1) return 1;
        //定义dp数组记录从0到n长度的绳子减掉后的最大乘积
        int[] dp = new int[n + 1];
        dp[2] = 1;
        //讨论长度＞＝3的绳子
        for (int i = 3; i < n + 1; i++) {
            // 对于长度为 i 的绳子，它可以分为两个区间 j 和 i - j
            // j 的范围由 2 开始，因为剪长度为 1 的绳子无法扩大乘积的值
            // j 的范围可以延伸至 i - 1
            for (int j = 2; j < i; j++) {
                // 不剪总长度乘积为  j * （ i - j）
                // 剪的话长度乘积为  j * dp[ i - j ]
                // 取两者的最大值，即  Max ( j * ( i - j) , j * dp[ i - j] )
                // 那么此时 dp[i] 的值取 i 不剪的值（ dp[i]) 和剪的值 Math.max(j * (i - j), j * dp[i - j]) 这两者的最大值
                // 比如一开始 i = 3 ， j = 2
                // dp[3] = Math.max( 0 ,Math.max ( 2 * 1, 2 * dp[1])
                //       = Math.max( 0 ,Math.max ( 2, 2))
                //       = 2
                dp[i] = Math.max(dp[i],Math.max(j * (i - j), j * dp[i - j]));
            }
        }

        return dp[n];
    }
}